/*
 *快速排序
 */

#include<iostream>
#include<vector>

using namespace std;
int  partition(vector<int> &nums,int lo,int hi)//切分
{
    int i=lo+1,j=hi;
    int num=nums[lo];
    while(true)
    {
        //找左边第一个大于num的值
        while(i<=hi&&nums[i]<num)
            ++i;
        //找右边第一个小于num的值
        while(j>=0&&nums[j]>num)
            --j;
        if(i>=j)
            break;
        swap(nums[i],nums[j]);
    }
    swap(nums[lo],nums[j]);
    return j;
}

void quick_sort(vector<int> &nums,int lo,int hi)
{
    if(lo>=hi)
        return;
    int j=partition(nums,lo,hi);
    quick_sort(nums,lo,j);
    quick_sort(nums,j+1,hi);
}

int main()
{
    vector<int> nums={1,2,15,0,5,34};
    quick_sort(nums,0,5); 
    for(auto num:nums)
    {
        cout<<num<<" ";
    }
    return 0;
}